// Copyright (c) 2016, Stefan Cloudt
// Permission to use, copy, modify, and/or distribute this software for any purpose
// with or without fee is hereby granted, provided that the above copyright notice
// and this permission notice appear in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
// OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

use std::cmp::Ordering;
use std::collections::VecDeque;

/// A sorted array that maintains its elements in sorted order.
pub struct SortedArray<T>
where
    T: Ord,
{
    data: Vec<T>,
}

impl<T> SortedArray<T>
where
    T: Ord,
{
    /// Creates a new empty `SortedArray`.
    pub fn new() -> Self {
        SortedArray { data: Vec::new() }
    }

    /// Returns the number of elements in the sorted array.
    pub fn len(&self) -> usize {
        self.data.len()
    }

    /// Inserts a new element into the sorted array, maintaining the sorted order.
    pub fn insert(&mut self, value: T) {
        let index = self.data.binary_search(&value).unwrap_or_else(|i| i);
        self.data.insert(index, value);
    }

    /// Removes the element at the specified index.
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if index < self.data.len() {
            Some(self.data.remove(index))
        } else {
            None
        }
    }

    /// Removes a range of elements from the sorted array.
    pub fn remove_range(&mut self, start: usize, len: usize) {
        if start + len <= self.data.len() {
            self.data.drain(start..start + len);
        }
    }

    /// Returns a reference to the element at the specified index.
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index)
    }

    /// Returns the index of the specified value, if it exists in the sorted array.
    pub fn index_of(&self, value: &T) -> Option<usize> {
        self.data.binary_search(value).ok()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    const TEST_SIZE: usize = 20;
    const TEST_ARRAY: [i32; TEST_SIZE] = [
        10, 12, 12, 1, 2, 3, 6, 7, 2, 23, 13, 23, 23, 34, 31, 9, 21, -2, -12, -4,
    ];
    const TEST_REMOVE_EL: usize = 15;
    const TEST_REMOVE_RANGE: usize = 7;
    const TEST_REMOVE_RANGE_LENGTH: usize = 4;

    /// Checks if the sorted array maintains the sorted property.
    fn check_sorted_prop<T>(sorted_array: &SortedArray<T>)
    where
        T: Ord,
    {
        for i in 1..sorted_array.len() {
            assert!(sorted_array.get(i - 1) <= sorted_array.get(i));
        }
    }

    /// Generates a sorted array filled with the elements from `TEST_ARRAY`.
    fn generate_sorted_array() -> SortedArray<i32> {
        let mut sorted_array = SortedArray::new();
        for &value in TEST_ARRAY.iter() {
            sorted_array.insert(value);
        }
        sorted_array
    }

    #[test]
    fn test_sorted_array_new_free() {
        let sorted_array = SortedArray::<i32>::new();
        assert_eq!(sorted_array.len(), 0);
    }

    #[test]
    fn test_sorted_array_insert() {
        let mut sorted_array = generate_sorted_array();
        check_sorted_prop(&sorted_array);

        for _ in 0..20 {
            let value = rand::random::<i32>() % 100;
            sorted_array.insert(value);
        }

        check_sorted_prop(&sorted_array);
    }

    #[test]
    fn test_sorted_array_remove() {
        let mut sorted_array = generate_sorted_array();
        let value = sorted_array.get(TEST_REMOVE_EL + 1).cloned();
        sorted_array.remove(TEST_REMOVE_EL);
        assert_eq!(sorted_array.get(TEST_REMOVE_EL), value);
        check_sorted_prop(&sorted_array);
    }

    #[test]
    fn test_sorted_array_remove_range() {
        let mut sorted_array = generate_sorted_array();
        let mut new = Vec::new();

        for i in 0..TEST_REMOVE_RANGE_LENGTH {
            new.push(sorted_array.get(TEST_REMOVE_RANGE + TEST_REMOVE_RANGE_LENGTH + i).cloned());
        }

        sorted_array.remove_range(TEST_REMOVE_RANGE, TEST_REMOVE_RANGE_LENGTH);

        for i in 0..TEST_REMOVE_RANGE_LENGTH {
            assert_eq!(sorted_array.get(TEST_REMOVE_RANGE + i), new.get(i));
        }

        check_sorted_prop(&sorted_array);
    }

    #[test]
    fn test_sorted_array_index_of() {
        let sorted_array = generate_sorted_array();

        for i in 0..TEST_SIZE {
            let value = sorted_array.get(i).unwrap();
            let index = sorted_array.index_of(value).unwrap();
            assert_eq!(sorted_array.get(index), Some(value));
        }
    }

    #[test]
    fn test_sorted_array_get() {
        let sorted_array = generate_sorted_array();

        for i in 0..sorted_array.len() {
            let value = sorted_array.get(i).unwrap();
            assert_eq!(sorted_array.get(i), Some(value));
        }
    }
}
